# 类名称：SElemType
# 类说明：数据元素类型
# 类释义：该类拥有带排序的关键字key
class StaticTableElement(object):
    def __init__(self, key):
        self.key = key


class IndexTableElement(object):
    def __init__(self, key, addr):
        self.key = key
        self.addr = addr


# 类名称：IndexTable
# 类说明：索引表的顺序存储结构
# 类释义：该类拥有同一个数据元素类型的列表data和data的长度length
class IndexTable(object):
    def __init__(self):
        self.data = []
        self.length = 0

    # 查找子表中的最大关键字
    def MaxBlockData(self, elements, m, n):
        maxdata = elements[m]
        for i in range(m, n):
            if maxdata < elements[i]:
                maxdata = elements[i]
        return maxdata

    # 创建索引表
    def CreateIndexTable(self, elements, n):
        self.length = n  # 分成n块
        num = int(len(elements) / n)  # 块内元素个数
        for i in range(self.length):
            self.data.insert(i, IndexTableElement(self.MaxBlockData(elements, i * num, (i + 1) * num), i * num))

    def TraverseIndexTable(self):
        print("待排序列表为：")
        for i in range(self.length):
            print(self.data[i].key, ' ', self.data[i].addr, '\t')


class StaticTable(object):
    def __init__(self):
        self.data = []
        self.length = 0

    # 创建数据元素类型列表
    def CreateSequenceTable(self, elements):
        self.length = len(elements)
        for i in range(self.length):
            self.data.append(StaticTableElement(elements[i]))

    # 打印待排序列表集合
    def TraverseSequenceTable(self):
        print("索引表每一索引项的key和addr分别为：")
        for i in range(self.length):
            print(self.data[i].key, end="\t")
        print()

    # 索引查找函数
    def IndexSearch(self, key, IndexTable):
        iPos = -1
        low = 0
        high = 0
        # num获得子块中的关键字个数
        num = IndexTable.data[1].addr - IndexTable.data[0].addr
        for i in range(IndexTable.length - 1):  # 防止溢出
            if key <= IndexTable.data[i].key:
                low = 0
                high = low + num
                break
            if IndexTable.data[i].key < key <= IndexTable.data[i + 1].key:
                low = IndexTable.data[i + 1].addr
                high = low + num
                break
        if high != 0:
            for i in range(low, high):
                if key == self.data[i].key:
                    iPos = i
            return iPos
        else:
            return iPos


# 主程序
STdata = [8, 3, 5, 10, 16, 25, 28, 35, 30, 56, 40, 55]
It = IndexTable()
It.CreateIndexTable(STdata, 12)
It.TraverseIndexTable()
ST = StaticTable()
ST.CreateSequenceTable(STdata)
ST.TraverseSequenceTable()
while True:
    iKey = input("请输入待查找关键字(#退出):")
    if iKey == '#':
        break
    STKey = int(iKey)
    STPos = ST.IndexSearch(STKey, It)
    if STPos == -1:
        print("在静态查找表中未找到关键字", STKey)
    else:
        print("关键字", STKey, "在静态查找表中的位置为：", STPos)
